var zigzagLevelOrder = function (root) {
    const queue = []
    if (!root) {
        return []
    }
    const arr = []
    queue.push(root)
    let flag = true
    while (queue.length) {
        const res = []
        const len = queue.length
        for (let i = 0; i < len; i++) {
            const top = queue.shift();
            if (flag) {
                res.push(top.val)
            }
            else {
                res.unshift(top.val)
            }



            if (top.left) {
                queue.push(top.left)
            }
            if (top.right) {
                queue.push(top.right)
            }
        }
        arr.push(res)
        flag = !flag
    }
    
    return arr
}

